package cuiyt.algorithm.graph;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;

/**
 * @author cyt
 * @create 2020-09-01 16:46
 */
public class Graph {
    static private ArrayList<String> node;
    static private int[][] edges;
    static private int edgesNum;
    static private boolean[] isVisited;

    public Graph(int n) {
        edgesNum = 0;
        node = new ArrayList<>(n);
        edges = new int[n][n];
        isVisited = new boolean[n];
    }

    /**
     * 使用的是 顶点数组的方式来创建
     *
     * @param args
     */
    public static void main(String[] args) {
        Graph graph = new Graph(5);
        String[] strings = {"a", "b", "c", "d", "e"};
        for (String s : strings) {
            addNodes(s);
        }
        addGraph(0, 1, 1);
        addGraph(1, 2, 1);
        addGraph(2, 3, 1);
        addGraph(3, 4, 1);
        addGraph(4, 0, 1);
        showGraph();

        // dfs(isVisited, 0);
        bfs(isVisited, 0);
    }

    /**
     * 广度优先遍历 使用队列来实现
     * 首先入队一个元素， 然后得到和这个元素下一层（距离相同）的元素加入到
     * 队列中 每次访问队中元素后， 出队此元素。
     */
    public static void bfs(boolean[] isVisited, int i) {
        int u;
        int w;
        LinkedList<Integer> queue = new LinkedList<>();
        queue.addLast(i);
        isVisited[i] = true;
        System.out.print(getValue(i) + "-> ");
        while (!queue.isEmpty()) {
            u = queue.removeFirst();
            w = getFirstNeighbor(u);
            while (w != -1) {
                if (!isVisited[w]) {
                    System.out.print(getValue(w) + "-> ");
                    isVisited[w] = true;
                    queue.addLast(w);
                }
                w = getNextNeighbor(u, w);
            }
        }
    }

    /**
     * 深度优先遍历
     */
    public static void dfs(boolean[] isVis, int i) {
        // 标记该节点访问过了, 因为不需要找最优解 所以不需要回溯
        isVis[i] = true;
        // 访问该节点
        System.out.print(getValue(i) + "-> ");
        int neighbor = getFirstNeighbor(i);
        while (neighbor != -1) {
            /**
             * 没有访问过这个节点
             */
            if (!isVis[neighbor]) {
                dfs(isVis, neighbor);
            }
            /**
             * 已经访问过这个节点
             */
            neighbor = getNextNeighbor(i, neighbor);
        }

    }

    /**
     * 根据前一个邻接结点的下标来获取下一个邻接结点
     *
     * @param v1
     * @param v2
     * @return
     */
    public static int getNextNeighbor(int v1, int v2) {
        for (int j = v2 + 1; j < node.size(); j++) {
            if (edges[v1][j] > 0) {
                return j;
            }
        }
        return -1;
    }

    /**
     * @param i
     * @return
     */
    public static String getValue(int i) {
        return node.get(i);
    }

    /**
     * 得到下一个最近的节点
     *
     * @param i
     * @return
     */
    public static int getFirstNeighbor(int i) {
        for (int i1 = 0; i1 < node.size(); i1++) {
            if (edges[i][i1] > 0) {
                return i1;
            }
        }
        return -1;
    }

    /**
     * 打印图
     */
    public static void showGraph() {
        for (int[] edge : edges) {
            System.out.println(Arrays.toString(edge));
        }
    }

    /**
     * 添加边
     *
     * @param x
     * @param y
     * @param ans
     */
    public static void addGraph(int x, int y, int ans) {
        edges[x][y] = ans;
        edges[y][x] = ans;
        edgesNum++;
    }

    /**
     * 添加节点
     *
     * @param nodes
     */
    public static void addNodes(String nodes) {
        node.add(nodes);
    }
}
